package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
Serling公司购买长钢条，将其切割为短钢条出售。
切割工序本身没有成本支出。
公司管理层希望知道最佳的切割方案。
假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。
钢条的长度均为整英寸。

长度i 	| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
		| -  | -  | -  | -  | -  | -  | -  | -  | -  | -  |
价格pi 	| 1  | 5  | 8  | 16 | 10 | 17 | 17 | 20 | 24 | 30 |

钢条切割问题是这样的：
给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，
求切割钢条方案，使得销售收益rn最大。
注意，
如果长度为n英寸的钢条的价格pn足够大，
最优解可能就是完全不需要切割!

10
1 5 8 16 10 17 17 20 24 30

37
 */
public class g钢条切割byDFS {
	public static void main(String[] args) {
		g钢条切割byDFS test = new g钢条切割byDFS();
		test.useDFS();
	}
	
	/**
	 * 前置方法
	 * 有大量重复子问题
	 */
	public void useDFS() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] price = new int[N];
		for (int i = 0; i < N; i++) {
			price[i] = scanner.nextInt();
		}
		int res = DFS(N, price);
		System.out.println(res);
	}
	
	/**
	 * 递归形式
	 * 不需要回溯。因为本方法的参数没有做状态改变
	 * 每次递归，传的参数是新的参数
	 * @param length
	 * @param price
	 * @return
	 */
	public int DFS(int length, int[] price) {
		if (length == 0) {//length代表传入的钢条全长
			return 0;//0就代表递归到底，没有东西可以切割了
		}
		int res = 0;
		/*
		 从最外的第一个for循环的视角看：
		i是当前固定片段的长度；
		一共有length个尝试；也就是说i可以有length个值
		当i = length，就代表不切
		price[i - 1]中的i - 1代表的就是下标，长度=i的钢条的价值是price[i-1]
		*/
		for (int i = 1; i <= length; i++) {//尝试所有可能
			//当前长度价值+剩余长度中的所有切割尝试中的最大价值
			int currentValue = price[i - 1] + DFS(length - i, price);
			//这个取最大值，就保证了上一条语句的“最大价值”
			res = Math.max(res, currentValue);//第一次一定是currentValue；随后不一定了
		}
		return res;
	}
}
